#!/usr/bin/env python

#Implementation by Alex Bendig
#http://www.notjustrandom.com/2009/11/13/finding-frequent-items-in-a-data-stream/

import numpy as np 
import operator
import pylru
from profilehooks import profile
import util
import ss_hash as ssum

class Bucket(object):
        def __init__(self, value = 1, elements = []):
                self.value = value
                self.elements = []


        def __str__(self):
                return "%s: %s" % (self.value, str(self.elements))

        def append(self, element):
                self.elements.append(element)

        def first_element(self):
                if self.elements:
                        return self.elements[0]
                else:
                        return None

        def has_elements(self):
                return len(self.elements) > 0

        def remove(self, element):
                self.elements.remove(element)

class StreamSummary(object):
        """
        Maintains a dictionary of elements and a list of buckets. Each element
        points to a (parent) bucket.
        The bucket list is sorted based on the buckets' values. Each bucket also
        maintains a list of elments.
        This has the effect of grouping elements with equal values in buckets.
        """
        def __init__(self, size):
                self.elements = {}
                self.buckets = []
                lru = pylru.lrucache(size)
                self.size = size

        def __len__(self):
                return len(self.elements.keys())

        def __str__(self):
                result = ""
                for b in self.buckets:
                        result += str(b) + " "
                return result

        def get_size(self):
            return self.size

        #@profile
        def add_element(self, element):
                """
                Adds an element and ensures it's assigned to the correct bucket.
                """
                if not self.elements.has_key(element):
                        if not self.buckets or self.buckets[0].value != 1:
                                self.buckets.insert(0, Bucket())
                        self.elements[element] = self.buckets[0]
                        self.buckets[0].elements.append(element)

        def increase_element(self, element):
                """
                Increasing an element's value also means assigning it to the
                correct bucket. That can result in creating a new bucket and/or
                removing an empty one.
                """
                current_bucket = self.elements[element]
                bucket_index = self.buckets.index(current_bucket)

                if len(self.buckets) == bucket_index + 1:
                        self.buckets.append(Bucket(value = current_bucket.value + 1))
                elif self.buckets[bucket_index + 1].value > current_bucket.value + 1:
                        self.buckets.insert(bucket_index + 1,
                                            Bucket(value = current_bucket.value + 1))
                current_bucket.remove(element)
                self.elements[element] = self.buckets[bucket_index + 1]
                if not current_bucket.has_elements():
                        del self.buckets[bucket_index]
                self.elements[element].append(element)

        def has_element(self, element):
                return self.elements.has_key(element)

        def get_minimum(self):
                if self.buckets:
                        return self.buckets[0].first_element()
                else:
                        return None

        def replace_element(self, old_element, new_element):
                """
                Replaces an existing element with an entirely new element in
                the old element's bucket.
                """
                self.elements[new_element] = self.elements[old_element]
                self.elements[new_element].remove(old_element)
                self.elements[new_element].append(new_element)
                del self.elements[old_element]

        def get_top(self, limit):


                if len(self.buckets) <= limit  :
                    return self.buckets
                else :
                    begin = len(self.buckets) - limit
                    return self.buckets[begin:]

        def add_to_ss(self, element) :
            if summary.has_element(element):
                    summary.increase_element(element)
            elif element in lru :
                if len(summary) < self.size :
                    summary.add_element(element)
                    summary.increase_element(element)
                else :
                    current_minimum_key = summary.get_minimum()
                    if current_minimum_key:
                        summary.replace_element(current_minimum_key, element)
                        summary.increase_element(element)
                    else :
                        summary.add_element(element)
                        summary.increase_element(element)
                del lru[element]
            else :
                lru[element] = 1


def space_saving_frequent_k_lru(k, stream):
        summary = StreamSummary(k)
        lru = pylru.lrucache(k)

        for element in stream:
                if summary.has_element(element):
                    summary.increase_element(element)

                elif element in lru :
                    if len(summary) < k :
                        summary.add_element(element)
                        summary.increase_element(element)
                    else :
                        current_minimum_key = summary.get_minimum()
                        if current_minimum_key:
                            summary.replace_element(current_minimum_key, element)
                            summary.increase_element(element)
                        else :
                            summary.add_element(element)
                            summary.increase_element(element)
                    del lru[element]
                else :
                    lru[element] = 1

        return summary

def space_saving_frequent_k(k, stream):
        summary = StreamSummary(k)
        for element in stream:
                if summary.has_element(element):
                        summary.increase_element(element)
                elif len(summary) < k:
                        summary.add_element(element)
                else:
                        current_minimum_key = summary.get_minimum()
                        if current_minimum_key:
                                summary.replace_element(current_minimum_key, element)
                                summary.increase_element(element)
                        else:
                                summary.add_element(element)
        return summary

size = 20
limit = 10
stream = np.random.zipf(2.8, 1000000)

def callback(*args, **kwargs):
    print (args, kwargs)

with util.Timer() as t :
    _summary_lru = space_saving_frequent_k_lru(size, stream)
print('Space saving lru took %.03f sec.' % t.interval)

with util.Timer() as t :
    _summary = space_saving_frequent_k(size, stream)
print('Space saving cache took %.03f sec.' % t.interval)

exact = {}

with util.Timer() as t :
    for item in stream :
        if item not in exact :
            exact[item] = 1
        else :
            exact[item] += 1
print('Exact summary took %.03f sec.' % t.interval)
#exact_sorted = OrderedDict(sorted(exact.items, key=lambda exact: exact[1] ) )
#for key in sorted(exact, key=operator.itemgetter(1), reverse=True) :
#    exact_sorted.append((key, exact[key]))
#exact = dict(zip(exact.values(), exact.keys()))
#exact_sorted = sorted(exact.items(), key=lambda(k,v):(v,k), reverse=True)
#exact_sorted = sorted(exact.items(), reverse=True)

_ss_lru = _summary_lru.get_top(limit)
_ss_lru.reverse()

_ss =  _summary.get_top(limit)
_ss.reverse()


print "exact\tsummary lru\tsummary: "
print "keys", _summary_lru.elements.keys()


#for item in zip(exact_sorted[:limit], _ss_lru, _ss) :
#    print item[0], "\t", item[1], "\t", item[2]

#with util.Timer() as t :
#    ss = ssum.StreamSummary(size)
#
#    for el in stream :
#        ss.insert(el)
#    #print "SS\n", ss
#print('Stream Summary took %.03f sec.' % t.interval)
#print "SS result\n", ss
#print ss.getelements().keys()